package com.spd.sort;

import java.util.Arrays;

/**
 * 快速排序
 * @author xianchao
 *
 */
public class QuickSort {

	private int[] array = null; //new int[]{2, 8, 7, 1, 3, 5, 6, 4};
	
	public void init(int[] array) {
		this.array = array;
	}
	
	/**
	 * 快速排序，按照递归的思路，每次调用，选择一个基准值，把小于基准值的放到标记
	 * 小的下标i的左边，大于基准值的放到i的右边。
	 * @param p
	 * @param r
	 */
	public void sort(int p, int r) {
		System.out.println("p:" + p + ", r:" + r);
		if(p < r) {
			int q = partition(p, r);
			sort(p, q - 1);
			sort(q + 1, r);
		}
	}
	
	/**
	 * p, r 两个指针，分别代表要排序的数组，或者子数组的最左，最右的下标
	 * @param p
	 * @param r
	 */
	public int partition(int p, int r) {
		//排序中的临时变量，分别表示小于基准值，大于基准值的元素下标
		int i = p - 1;
		for(int j = p; j < r; j++) {
			if(array[j] <= array[r]) {
				i++;
				int temp = array[j];
				array[j] = array[i];
				array[i] = temp;
			}
		}
		//最后依次，把基准值 r 和下标为i + 1的元素进行交换
		int temp = array[r];
		array[r] = array[i + 1];
		array[i + 1] = temp;
		return i + 1;
	}
	
	public static void main(String[] args) {
		int[] array = new int[]{2, 8, 7, 1, 3, 5, 6, 4};
		QuickSort quickSort = new QuickSort();
		quickSort.init(array);
		quickSort.sort(0, array.length - 1);
		System.out.println(Arrays.toString(array));
	}
}
